package leetcode.d_300_plus;

public class P300 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n]; // 代表索引i处的最长子序列长度
        for (int i=0; i<n; i++) {
            dp[i] = 1; // 默认都为1，即只有当前这一个数
        }
        int maxLen = 1;
        for(int i=1; i<n; i++) {
            for (int j=0; j<i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            maxLen = Math.max(maxLen,  dp[i]);
        }
        return maxLen;
    }
}
